package com.wc.alorithm.tree;

/**
 * @Author congege
 * @Description 无旋树堆
 * @Date Created in 2023/12/22-15:59
 */

public class Fhotreap {
    static int maxN = (int) 1e5 + 10;
    int root;
    int size;
    Node[] nodes = new Node[maxN];

    static class Pair {
        Pair() {
            this(0, 0);
        }

        Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }

        int first;
        int second;
    }

    static class Tuple {
        Tuple() {
            this(0, 0, 0);
        }

        Tuple(int l, int mid, int r) {
            this.l = l;
            this.mid = mid;
            this.r = r;
        }

        int l;
        int mid;
        int r;
    }

    // [1,val] (val,最大)
    Pair spiltByVal(int t, int val) {
        if (nodes[t] == null) {
            return new Pair();
        }
        pushDown(t);
        if (nodes[t].val <= val) {
            Pair tmp = spiltByVal(nodes[t].ch[1], val);
            nodes[t].ch[1] = tmp.first;
            pushUp(t);
            return new Pair(t, tmp.second);
        } else {
            Pair tmp = spiltByVal(nodes[t].ch[0], val);
            nodes[t].ch[0] = tmp.second;
            pushUp(t);
            return new Pair(tmp.first, t);
        }
    }

    Tuple splitByRank(int t, int k) {
        if (nodes[t] == null) {
            return new Tuple();
        }
        pushDown(t);
        int l, m, r;
        if (k <= nodes[nodes[t].ch[0]].size) {
            Tuple tmp = splitByRank(nodes[t].ch[0], k);
            nodes[t].ch[0] = tmp.r;
            pushUp(t);
            return new Tuple(tmp.l, tmp.mid, t);
        } else if (k > nodes[nodes[t].ch[0]].size + nodes[t].cnt) {
            Tuple tmp = splitByRank(nodes[t].ch[1], k - nodes[nodes[t].ch[0]].size - nodes[t].cnt);
            nodes[t].ch[1] = tmp.l;
            pushUp(t);
            return new Tuple(t, tmp.mid, tmp.r);
        } else {
            l = nodes[t].ch[0];
            r = nodes[t].ch[1];
            pushDown(l);
            pushDown(r);
            nodes[t].ch[0] = 0;
            nodes[t].ch[1] = 0;
            pushUp(t);
            return new Tuple(l, t, r);
        }
    }

    void pushUp(int t) {
        int size = nodes[t].cnt;
        size += nodes[nodes[t].ch[0]].size;
        size += nodes[nodes[t].ch[1]].size;
        nodes[t].size = size;
    }

    void pushDown(int t) {
        if (nodes[t].rev) {
            swap(t);
            nodes[nodes[t].ch[0]].rev ^= true;
            nodes[nodes[t].ch[1]].rev ^= true;
            nodes[t].rev = false;
        }
    }

    void swap(int t) {
        int tmp = nodes[t].ch[0];
        nodes[t].ch[0] = nodes[t].ch[1];
        nodes[t].ch[1] = tmp;
    }
}


class Node {
    // 权值
    int val;
    // 数量
    int cnt;
    // 反转标记
    boolean rev;
    // 优先级
    int prio;
    // 子树大小
    int size;

    int[] ch = new int[2];
}
